Atomicity for MacHack 99

Prev Next

Atomicity:

Concurrent Data Access Without Blowing Up

Prev Next

Overview

What is Atomicity?
An example: Alice and Bob
Another example: Incrementing a shared counter
The Window of Death
PowerPC Atomicity
68K Atomicity
Atomic Data Structures

Prev Next

What is Atomicity?

Atomicity is the solution to the problem of concurrent data access.
Tasks are comprised of a series of steps.
Often, between the first step and the last step, data will be put into an inconsistent state.
If another program accesses the data before the task is completed, the program may access corrupt or stale data.

Prev Next

An example: Alice and Bob

Alice and Bob run an unsuccessful organized crime ring.
Alice prints up $10 bills at Kinko's on the north side of town.
Bob collects "insurance" from shopkeeps on the south side of town.
At the end of each day, they deposit their money into a joint bank account.
Today, Alice printed up 10 $10 bills for $100. Bob collected $200 worth of premiums. Their bank account currently holds $1,000.

Prev Next

Alice and then Bob

Prev Next

Bob and then Alice

Prev Next

Alice and Bob at the same time

Prev Next

Example 2: Incrementing a Shared Counter

In my paper:
unsigned long gConnectCount;
void IncrementConnectCount() { ++gConnectCount; }

Prev Next

PowerPC Instructions

lwz r3, gConnectCount(rtoc) Load address of gConnectCount into register r3.

lwz r4, 0(r3) Load integer from RAM into register r4.

addi r4, r4, 1 Add 1 to register r4.

stw r4, 0(r3) Store incremented value from register r4 back into RAM.

blr Return from subroutine.

Prev Next

IncrementConnectCount() Once

Prev Next

IncrementConnectCount() Twice

Prev Next

IncrementConnectCount() Concurrently

Prev Next

Fighting the Window of Death

Turn on the optimizers!
Load/store versus 68K.
- PowerPC: load, add, store
- 68K: add
68K add is atomic

Prev Next

PowerPC Atomicity

Load Word And Reserve Index (lwarx)
Store Word Conditional Index (stwcx.)
- Atomically alter one 32 bit value

Prev Next

68K Atomicity

Compare and Swap (cas)
- Atomically alter one 32 bit value
Compare and Swap 2 (cas 2)
- Atomically alter two 32 bit values
- Atomic Doubly Linked Lists!

Prev Next

Atomic Data Structures

Atomic Stacks
Atomic Locks
Atomic Queues

Prev Next

Atomic Stacks

I put my atomic stack code on the CD.
Open Transport also provides atomic stacks (LIFO Lists).
Stacks are fast and easy but not flexible.
Open Transport allows you to morph a stack into a more useful queue.
- Atomically "steal" the stack
- Non-atomically "reverse" the stack into a "First In, First Out" Linked List.
I provide atomic queues -- no non-atomic operations from user's viewpoint.

Prev Next

Atomic Stacks Are Easy to Corrupt

Prev Next

Atomic Locks

I put my atomic lock code on the CD, and Open Transport provides atomic locks.

Atomic Locks provide protection for data structures.

Attempt to "acquire" a resource.

On success, the lock is atomically set to non-zero.
- Otherwise nothing is changed and the acquisition fails.
  - The act of releasing a resource is simply setting its lock to zero.
  Prev Next
  Atomic Queues
  - Popping is more complicated:
    - Attempt to pop off the output stack.
    - If the output stack is empty, then it needs "refilling".

`lwz`	`r3, gConnectCount(rtoc)`	Load address of gConnectCount into register r3.
`lwz`	`r4, 0(r3)`	Load integer from RAM into register r4.
`addi`	`r4, r4, 1`	Add 1 to register r4.
`stw`	`r4, 0(r3)`	Store incremented value from register r4 back into RAM.
`blr`		Return from subroutine.